package 动态规划9月;
// https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=188&&tqId=38613&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
public class NC29二维数组中的查找0928 {
    public class Solution {
        //     public boolean Find(int target, int [][] array) {
//         for(int i=0;i<array.length;i++){
//             for(int j=0;j<array[0].length;j++){
//                 if(target==array[i][j]){
//                     return true;
//                 }
//             }
//         }
//         return false;
//     }  o(n*n)
        public boolean Find(int target, int [][] array) {
            int rows = array.length;
            if(rows == 0){
                return false;
            }
            int cols = array[0].length;
            if(cols == 0){
                return false;
            }
            // 左下
            int row = rows-1;
            int col = 0;
            while(row>=0 && col<cols){
                if(array[row][col] < target){
                    col++;
                }else if(array[row][col] > target){
                    row--;
                }else{
                    return true;
                }
            }
            return false;
        }


//     public boolean Find(int target, int [][] array) {
//         int rows = array.length;
//         if(rows == 0){
//             return false;
//         }
//         int cols = array[0].length;
//         if(cols == 0){
//             return false;
//         }
//         // 右上
//         int row = 0;   //注意
//         int col = cols-1;    //注意
//         while(row<rows && col>=0){    //注意
//             if(array[row][col] < target){
//                 row++;        //注意
//             }else if(array[row][col] > target){
//                 col--;      //注意
//             }else{
//                 return true;
//             }
//         }
//         return false;
//     }
    }
}
